package com.dh.leetcode.six;

import com.dh.leetcode.common.TreeNode;
import com.dh.leetcode.common.TreeNodeIterator;
import org.junit.Assert;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * ClassName: _671_second_minimum_node_in_a_binary_tree
 *
 * @author shouzimu
 * @Description: 671. 二叉树中第二小的节点
 * 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。
 * 如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
 * <p>
 * 更正式地说，root.val = min(root.left.val, root.right.val) 总成立。
 * <p>
 * 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [2,2,5,null,null,5,7]
 * 输出：5
 * 解释：最小的值是 2 ，第二小的值是 5 。
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [2,2,2]
 * 输出：-1
 * 解释：最小的值是 2, 但是不存在第二小的值。
 *
 * https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
 *
 * @date 2021/7/27 21:18
 */
public class _671_second_minimum_node_in_a_binary_tree {

    /**
     * 广度优先遍历
     * @param root
     * @return
     */
    public int findSecondMinimumValue(TreeNode root) {
        int rootVal = root.val;
        int res = -1;
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        boolean less = true;
        while (!nodes.isEmpty()) {
            int size = nodes.size();
            for (int i = 0; i < size; i++) {
                TreeNode v = nodes.poll();
                if (v.val > rootVal) {
                    if (less) {
                        res = v.val;
                        less = false;
                    } else {
                        res = Math.min(res, v.val);
                    }
                }
                if (null != v.left) {
                    nodes.add(v.left);
                }
                if (null != v.right) {
                    nodes.add(v.right);
                }
            }
        }
        return res;
    }

    @Test
    public void findSecondMinimumValueTest() {
        TreeNode node = TreeNodeIterator.initTestTree(new Integer[]{2, 2, 5, null, null, 5, 7});
        Assert.assertEquals(5, findSecondMinimumValue(node));

        node = TreeNodeIterator.initTestTree(new Integer[]{2, 2, 2});
        Assert.assertEquals(-1, findSecondMinimumValue(node));

        node = TreeNodeIterator.initTestTree(new Integer[]{5, 8, 5});
        Assert.assertEquals(8, findSecondMinimumValue(node));
    }
}
